package DataStructrue;

import java.util.*;

//排序算法
public class Sorts {
    //选择排序(稳定)
    public static void selectSort(int[] arr){
        int n=arr.length;
        //从第一个开始,遍历之后的数,寻找最小值,交换到前面
        for (int i=0; i<n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[i]) {
                   int tmp=arr[i];
                   arr[i]=arr[j];
                   arr[j]=tmp;
                }
            }
        }
    }
    //冒泡排序(稳定)
    public static void bubbleSort(int[] arr){
        int n=arr.length;
        //检查相邻数的顺序是否正确,每次最小的数排到前面
        while (true) {
            boolean flag = false;//是否有交换,没有说明有序
            for (int i = n-1; i >=1; i--) {
                if (arr[i] < arr[i - 1]) {
                    flag = true;
                    int tmp = arr[i];
                    arr[i] = arr[i - 1];
                    arr[i - 1] = tmp;
                }
            }
            if(!flag) break;
        }
    }
    //插入排序(稳定)
    public static void insertSort(int[] arr){
        int n=arr.length;
        //选择后面的某个数,插入到前面的有序序列
        for (int i = 0; i < n - 1; i++) {
            int end = i;//end前为有序序列
            int tmp = arr[end + 1];//取出待插入的数
            //向前寻找,直到遇到第一个不大于tmp的位置
            while (end >= 0) {
                if (arr[end] > tmp) {
                    arr[end + 1] = arr[end];//大于则向后移动数字
                    end--;
                } else break;
            }
            arr[end + 1] = tmp;//放置tmp
        }
    }
    //希尔排序(不稳定)
    public static void shellSort(int[] arr){
        int n=arr.length;
        //分成多组进行插入排序,最后成为一组
        int gap = n;
        while (gap > 1) {
            gap = gap / 2;//距离为gap的为一组
            //组内进行插入排序
            for (int i = 0; i < n - gap; i++) {
                int end = i;
                int tmp = arr[end + gap];//取出待插入的数
                //向前寻找,直到遇到第一个不大于tmp的位置
                while (end >= 0) {
                    if (arr[end] > tmp) {
                        arr[end + gap] = arr[end];
                        end -= gap;
                    } else break;
                }
                arr[end + gap] = tmp;
            }
        }
    }
    //计数排序(稳定)
    public static void countSort(int[] arr){
        int n=arr.length;
        //将所有数计数,再按顺序取出
        int[] cnt=new int[1000001];//记录索引数字出现的次数
        for (int k : arr) {
            cnt[k]++;
        }
        int idx=0;
        for (int i = 0; i < cnt.length; i++) {
            if(cnt[i]==0)
                continue;
            for (int j = 0; j < cnt[i]; j++) {
                arr[idx++]=i;
            }
        }
    }
    //基数排序(稳定)
    public static void radixSort(int[] arr){
        int n=arr.length;
        //从个位开始将所有位从低到高排序
        int max = arr[0];//最大值
        for (int val : arr) {
            if (max < val)
                max = val;
        }
        int len = max==0?1:0;//最大值位数
        while(max>0){
            len++;
            max/=10;
        }
        int base=1;
        for (int i = 0; i < len; i++) {
            int[][] tmp=new int[10][n];//存储arr中属于i位的数
            int[] idx=new int[10];//tmp中i位下一个添加位
            //根据数字的某一位加入到对应位的组
            for (int j = 0; j < n; j++) {
                int bit=arr[j]/base%10;//获取某一位
                tmp[bit][idx[bit]++]=arr[j];
            }
            //放回arr
            int next=0;
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < idx[j]; k++) {
                    arr[next++]=tmp[j][k];
                }
            }
            base*=10;
        }
    }
    //快速排序(不稳定),分治算法
    public static void quickSort(int[] arr){
        quickSort(arr,0,arr.length-1);
    }
    private static void quickSort(int[] arr,int begin,int end){
        if(begin>=end)
            return;
        int pivot = arr[(begin+end)>>1];//取基准数
        int idx = begin, l = begin, r = end;
        // 完成一趟三路快排，将序列分为:
        // 小于 pivot 的元素｜ 等于 pivot 的元素 ｜ 大于 pivot 的元素
        while (idx <= r) {
            if (arr[idx] < pivot){//小于放到左边,idx处的数一定<=pivot,idx+1
                int tmp=arr[idx];
                arr[idx++]=arr[l];
                arr[l++]=tmp;
            } else if (arr[idx]>pivot){//大于放到右边,再判断idx处的数的大小
                int tmp=arr[idx];
                arr[idx]=arr[r];
                arr[r--]=tmp;
            }else
                idx++;
        }
        // 递归完成对于两个子序列的快速排序
        quickSort(arr, begin,l-1);
        quickSort(arr,r+1, end);
    }
    //归并排序(稳定),分治算法
    public static void mergeSort(int[] arr){
        mergeSort(arr,0,arr.length-1);
    }
    private static void mergeSort(int[] arr,int begin,int end){
        if(begin>=end)
            return;
        int mid=(begin+end)>>1;
        //左右递归分别排序,再进行合并
        mergeSort(arr,begin,mid);
        mergeSort(arr,mid+1,end);
        int[] tmp=new int[end-begin+1];//存储合并数组
        int idx = 0;//tmp的添加索引
        int begin1 = begin;
        int begin2 = mid + 1;
        //左右合并
        while (begin1 <= mid && begin2 <= end)
        {
            if (arr[begin1] < arr[begin2])
                tmp[idx++] = arr[begin1++];
            else
                tmp[idx++] = arr[begin2++];
        }
        while (begin1 <= mid)
            tmp[idx++] = arr[begin1++];
        while (begin2 <= end)
            tmp[idx++] = arr[begin2++];
        idx=0;//放回原数组
        for (int i = begin; i <= end; i++,idx++) {
            arr[i]=tmp[idx];
        }
    }
    //桶排序(稳定)
    public static void bucketSort(int[] arr){
        int n=arr.length;
        //桶代表一定范围,将数放入对应桶中,同时插入排序,最后按顺序遍历桶取出
        int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            min=Math.min(min,arr[i]);
            max=Math.max(max,arr[i]);
        }
        int m=(max-min)/10+1;//桶的数量
        int[][] bucket=new int[m][n];//存储属于某个范围的数
        int[] idx=new int[m];//桶的添加索引
        for (int i = 0; i < n; i++) {
            int num=(arr[i]-min)/10;//计算桶号
            int end=idx[num]++-1;
            //对该桶进行插入排序
            while (end >= 0) {
                if (bucket[num][end] > arr[i]) {
                    bucket[num][end + 1] = bucket[num][end];//大于则向后移动数字
                    end--;
                } else break;
            }
            bucket[num][end + 1] = arr[i];//放置tmp
        }
        int next=0;//放到原数组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < idx[i]; j++) {
                arr[next++]=bucket[i][j];
            }
        }
    }
    //堆的向下调整
    private static void adjustDown(int[] arr, int n, int root) {
        int parent = root;
        int child = 2 * parent + 1;
        //存在子节点则进行调整
        while (child <= n) {
            //取子节点较大者
            if (child + 1 <= n && arr[child] < arr[child + 1])
                child++;
            //将父子节点中最大者放到根部
            if (arr[child] > arr[parent]) {
                int tmp=arr[child];
                arr[child]=arr[parent];
                arr[parent]=tmp;
                //递归调整
                parent = child;
                child = 2 * parent + 1;
            } else//调整合适
                break;
        }
    }
    //堆排序(不稳定)
    public static void heapSort(int[] arr){
        int n=arr.length;
        //从最后一个节点的父节点开始,将整个数组调整为大堆
        for (int i = (n - 1 - 1) / 2; i >= 0; i--){
            adjustDown(arr, n-1, i);
        }
        int end = n - 1;
        //将最大值放在最后,最小值放在堆顶,再进行调整
        while (end>0) {
            int tmp=arr[0];
            arr[0]=arr[end];
            arr[end--]=tmp;
            adjustDown(arr, end, 0);
        }
    }
    //获取排序后对应的原数组索引
    public static int[] originIndex(int[] arr){
        int n=arr.length;
        int[][] tuple=new int[n][2];
        for (int i = 0; i < n; i++) {
            tuple[i][0]=arr[i];
            tuple[i][1]=i;
        }
        Arrays.sort(tuple,(a,b)->a[0]-b[0]);
        return tuple[1];
    }
    //将原数组替换为排序后的索引(离散化,会产生区间合并问题)
    public static int[][] sortIndex(int[] arr){
        int n=arr.length;
        //去重排序
        Set<Integer> s=new TreeSet<>();
        for (int i : arr) {
            s.add(i);
        }
        int[][] ans= {new int[s.size()],new int[n]};//第一行为排序数组,第二行为索引
        int cur=0;
        for (int i : s) {
            ans[0][cur++] = i;
        }
        for (int i = 0; i < n; i++) {
            ans[1][i]=Arrays.binarySearch(ans[0],ans[1][i]);
        }
        return ans;
    }







}
